<script>
  //   给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

  //   整数 a 比整数 b 更接近 x 需要满足：

  //   |a - x| < |b - x| 或者
  //   |a - x| == |b - x| 且 a < b
  //

  //   来源：力扣（LeetCode）
  //   链接：https://leetcode.cn/problems/find-k-closest-elements

  //   示例 1：

  //   输入：arr = [1,2,3,4,5], k = 4, x = 3
  //   输出：[1,2,3,4]
  //   示例 2：

  //   输入：arr = [1,2,3,4,5], k = 4, x = -1
  //   输出：[1,2,3,4]

  /**
   * 思路分析
   * 二分查找+双指针
   * 实现一个二分查找 内部主要注意 这里需要拿到 最接近 x 的数的下标
   * 双指针 判断区间 注意边界判定
   * left < 0 right++
   * right > arr.length left--
   * 满足一个公式 x - arr[left] <= arr[right] - x left --
   * 否则 right++
   * 最终 k-- > 0 走完 拿到一个区间 [left+1,right-1] 遍历这个区间的值即可
   */

  /**
   * @param {number[]} arr
   * @param {number} k
   * @param {number} x
   * @return {number[]}
   */
  var findClosestElements = function (arr, k, x) {
    let right = binarySearch(arr, x); // 2
    let left = right - 1; // 1
    while (k-- > 0) {
      if (left < 0) {
        right++;
      } else if (right >= arr.length) {
        left--;
      } else if (x - arr[left] <= arr[right] - x) {
        left--;
      } else {
        right++;
      }
    }
    const ans = [];
    for (let i = left + 1; i <= right - 1; i++) {
      ans.push(arr[i]);
    }
    return ans;
  };

  var binarySearch = function (arr, x) {
    let low = 0,
      high = arr.length - 1;
    while (low < high) {
      let mid = ((low + high) / 2) | 0;
      if (arr[mid] >= x) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return low;
  };
</script>
